Hash functions constructions are used in many algorithms and cryptographic protocols. They are functions ƒ: U→S with |U|≧|S| that distribute their image “uniformly”. In other words for most
                                          x            ∈            U                    ,                            ⁢              {                                            y              ∈              U                        ❘                          f              ⁡                              (                x                )                                              =          y                }                  ⁢          ⁢  is  ⁢          ⁢  close  ⁢          ⁢  to  ⁢          ⁢                            U                                    S                      .  
Hash functions that minimize the number of colliding pairs i.e., pairs (x, y) such that ƒ(x)=ƒ(y) are very useful. For cryptographic applications of hash functions, it is typically desired for the problem of engineering collisions to be hard. This means the task of finding distinct elements x and y such that ƒ(x)=ƒ(y) is computationally hard. Often, there is interest in the following weaker property: Given x finding another y such that ƒ(x)=ƒ(y) is hard.